\chapter{Algorytm pszczeli}
\thispagestyle{fancy}
  \section{Opis algorytmu}
Algorytm pszczeli jest jednym z algorytmów wzorowanych na naturze. Wykorzystuje zachowanie się
pszczół przy znajdowaniu pożywienia.
Istnieje wiele odmian tego algorytmu, jednak my skorzystaliśmy z wersji Artificial Bee Colony (ABC).

W tym algorytmie pszczoły są podzielone na ze względu na swoje role:
\begin{itemize}
 \item robotnicy (ang. employed bees) - związane z danym źródłem pokarmu, o którym zdają relację w ulu
 \item obserwatorzy (ang. onlookers)  - oglądają tzw. taniec wykonywany przez robotnice
 \item zwiadowcy (ang. scouts) - szukają pożywienia (w sposób losowy)
\end{itemize}
Zwiadowcy wyruszają na poszukiwanie nektaru. Po znalezieniu, wracają do ula by poinformować
obserwatorów gdzie znajduje się pożywienie oraz jaka jest jego jakość. Obserwatorzy w 
zależności od atrakcyjności, wybierają miejsce do którego polecą. Im bardziej atrakcyjne miejsce,
tym więcej obserwatorów do niego poleci stając się robotnikami. Wynika stąd, że pszczoły dążą
do zmaksymalizowania dostawy nektaru.
Ponieważ ilość nektaru cały czas się zmienia, zawsze działają zwiadowcy, którzy po odkryciu 
zasboniejszych źródeł, mogą zmienić miejsce eksploracji nektaru.

  \section{Struktura algorytmu}
Algorytm ma charakter iteracyjny, a każda iteracja składa się z następujących kroków:
\begin{itemize}
 \item Inicjalizacja
 \item Wysłanie robotnic
 \item Ocena znalezionych źródeł
 \item Wysłanie zwiadowców
\end{itemize}
Wszystkie kroki, oprócz Inicjalizacji, wykonywane są cyklicznie, do osiągnięcia maksymalnej ilości iteracji.

  \section{Dyskretna wersja problemu}
Algorytm pszczeli służy do znalezienia minimum funkcji celu:

\begin{math}
 f(\vec{x}), \vec{x} = (x_1, x_2,...,x_n) \in {\mathbb{R}^n}
\end{math}

W naszej implementecji przyjęliśmy najprostszy model dyskretyzacji, czyli założyliśmy, że nasza przestrzeń to
\begin{math}
  \mathbb{N}
\end{math}

A funkcja celu ma postać dyksretną:

\begin{math}
 f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}
\end{math}

Funkcja celu jest rekurencyjna. Warunki brzegowe to czas wykonania pierwszego zadania oraz czas wykonania pierwszego zadania pierwszej maszyny.
Całkowity czas zakończenia wynosi:

\begin{math}
 f(0, 0) = C_1
\end{math}

\begin{math}
 f(0, 1) = C_2
\end{math}

\begin{math}
 f(1, 0) = C_3
\end{math}

\begin{math}
 f(job, machine) = max(f(job - 1, machine), f(job, machine - 1)) + C(job, machine)
\end{math}

gdzie: \begin{math} C(job, machine) \end{math} zwraca czas wykonania zadania 
\begin{math}job\end{math} na maszynie \begin{math}machine\end{math}


  \subsection{Inicjalizacja}
Na etapie inicjalizacji ustalane są dostępne parametry algorytmu:
\begin{itemize}
 \item ilość iteracji, będące kryterium stopu,
 \item ilość źródeł pożywienia - odpowiada ilości robotnic,
 \item ilość obserwatorów - domyślnie jest dwa razy większa od ilości robotnic,
 \item ilość zwiadowców - domyślnie 0,2 ilości robotnic,
 \item stopień modyfikacji atrakcyjności źródła,
 \item wybór czy poszukiwanie ma odbywać się lokalnie przez robotnice i obserwatorów
 \item sposób poprawy rozwiązania przez zwiadowców - usunięcie najgorszego wyniku, czy wyniku którego najdłużej nie udało się zoptymalizować
\end{itemize}

Ponadto tworzone jest losowe rozwiązanie, które następnie będzie poprawiane przez pszczoły.

  \subsection{Wysłanie robotników}
Każda robotnica szuka w swoim otoczeniu zasobniejszych źródeł nektaru. Następnie obliczona zostaje 
atrakcyjność tego źródła. W naszym problemie szeregowania zadań przyjęłiśmy za bardziej atrakcyjne
rozwiązanie, to które bedzie miało mniejszy czas wykonania na wszystkich maszynach.
Czas ten jest równy czasowi zakończenia ostatniego zadania. Każde zadanie, oprócz pierwszego,
jest wstrzymane przez poprzednie wykonywane zadanie oraz przez wykonywanie obecnego zadania
na poprzedniej maszynie. Maksimum z obu czasów jest czasem zakończenia obecnego zadania.
Jeśli zmienione rozwiązanie okaże się lepsze, zastępuje stare rozwiązanie.

  \subsection{Ocena znalezionych źródeł}
Obserwatorzy oglądając taniec robotnic, decydują się na eksplorację najzasobniejszych źródeł.
W naszej implementecji zdecydowaliśmy jednak, że każdy obserwator wyrusza do najgorszego miejsca,
by je usunąć. Zamiast niego, pojawia się informacja o losowym miejscu. 

  \subsection{Wysłanie zwiadowców}
Każdy zwiadowca wybiera losowo dwa miejsca i sprawdza ich zasobność. Atrakcyjniesze z nich zostanie
eksplorowane i przedstawione obserwatorom.

  \section{Kod źródłowy}

  \subsection{Inicjalizacja}
Inicjalizacja wykonywana jest w dwóch częściach:
\begin{itemize}
 \item w konstruktorze pobierane są parametry algorytmu, które są dostarczane od GUI
 \item w metodzie init - tworzącej losowe rozwiązanie. Metoda jest wywoływana dla każdej robotnicy
\end{itemize}

Każda robotnica jest wektorem rozwiązań, stąd metoda init tworzy dla każdej z robotnic tworzy losowe ustawienie zadań.


  \subsection{Wysłanie robotników}
Kod dla tej metody jest bardzo prosty. Dla każdej pszczoły-robotnicy wywoływana jest funkcja
\texttt{findNeighborhoodSolution}

opisana przy ocenie znalezionych źródeł. Jest odpowiedzialna za znalezienie nowych źródeł w sąsiedztwie
ich obecnego położenia.

Kod:
\begin{lstlisting}
public void sendEmployedBees() {
  int i;
  for (i = 0; i < foodSourcesNumber_; i++) {
    findNeighborhoodSolution(i);
  }
}
\end{lstlisting}

  \subsection{Ocena znalezionych źródeł}
Każdy obserwator wybiera losowo dwie robotnice, których taniec będzie oglądał.
Każda robotnica reprezentuje możliwy układ zadań. Obserwator wybiera to rozwiązanie, które
ma krótszy czas wykonania i zaczyna je zmieniać, czyli udaje się do sąsiedztwa orygianlnego rozwiązania.

Zmiana jest wykonywana w metodzie
\texttt{findNeighborhoodSolution}

Otrzymane rozwiązanie jest zmieniane w metodzie 
\texttt{mutate}.

Jeśli zmienione rozwiązanie jest gorsze od początkowego, zwiększany jest dla niego licznik prób,
co jest jednym z kryteriów poprawy w fazie zwiadowców. W przeciwnym razie licznik jest ustawiany na zero.

Jeśli opcja wyszukiwania lokalnego jest włączona, niezależnie od oceny nowego rozwiązania, zaczyna się lokalna
poprawa rozwiązania. Podobnie jak wyżej, gdy nie uda się poprawić rozwiązania, zwiększany jest licznik prób,
a zerowany gdy uda się znaleźć lepsze rozwiązanie.

    \subsubsection{Poszukiwanie lokalne}
Jest zawarte w funkcji:
\texttt{VNS}.

Lokalne polepszanie rozwiązania polega na cyklicznej zamianie rozwiązania już zmienionego (przez funkcję mutate),
aż do czasu uzyskania lepszego wyniku. Lokalne polepszanie składa się z dwóch części.

W pierwszym etapie następuje próba poprawy rozwiązania przez wstawienie każdego zadania w każde możliwe miejsce.
Wykonywane jest w funkcji \texttt{insertLS}.
Czyli rozwiązanie będzie ``rozsuwane'' by w odpowiednie miejsce wstawić wybrane zadanie.
Po każdej zamianie następuje jego ocena. Jeśli jest lepsze, to zostaje zapamiętane.
Po zakończeniu tego etapu zwracane jest najlepsze rozwiązanie jakie udało się uzyskać i jest ono przekazywane do następnego etapu.

W tym etapie wykonywana jest próba poprawy przez zamianę każdych dwóch zadań ze sobą,
tzn. próba zamiany 1 z n, 1 z n - 1, ..., 1 z 2. Następnie 2 z n, 2 z n - 1, ..., 2 z 3.
Wykonywane jest w funkcji \texttt{swapLS}.
Jeśli tylko uda się uzyskać lepszy wynik, jest on zapamiętywany. Po zakończeniu tej procedury 
zwracany jest najlepszy wynik jaki udało się w ten sposób uzyskać. 

    \subsubsection{Zmiana rozwiązania}
Wykonywana jest w funkcji \texttt{mutate}

Polega na zmodyfikowaniu wzorcowego rozwiązania na jeden z pięciu sposobów:
\begin{itemize}
 \item Dokonanie jednej zmiany.
Program losowo wybiera dwa zadania, a następnie zamienia je ze sobą.

 \item Dokonanie jednego wstawienia.
Program losowo wybiera dwa zadania. Następnie odpowiednio ,,rozsuwa'' zadania, tak by pierwsze wybrane
wstawić na miejscu drugiego. Działa identycznie jak druga część poszukiwania lokalnego.

 \item Dokonanie dwóch zamian.
Działa analogicznie jak pierwszy sposób, ale dokonuje jeszcze jedną zamianę.

 \item Dokonanie dwóch wstawień
Podobnie jak powyżej, z tym że wykonuje jeszcze jedną zamianę.

 \item Losowo wybrany jeden z czterech powyższych sposobów
\end{itemize}

  \subsection{Wysłanie zwiadowców}
Każdy zwiadowca jest odpowiedzialny za usunięcie najgorszego rozwiązania.
Algorytm uwzględnia dwie możliwości klasyfikowania nieoptymalności rozwiązania:
\begin{itemize}
 \item (1) Łączny czas wykonania dla danej permutacji zadań,
 \item (2) Ilość prób poprawy danego rozwiązania przez robotnice.
\end{itemize}

Na początku tworzona jest pusta lista zawierająca poprawione już rozwiązania, a następnie dochodzi do poprawy rozwiązań.

W (1) przypadku każdy zwiadowca wyszukuje robotnicę z njagorszym wynikiem. W trakcie wyszukiwania
uwzględnia, czy dane rozwiązanie nie było już poprawiane. Jeśli było - nie jest brane pod uwagę.

Po znalezieniu najgorszego wyniku jest on zastepowany losowym ułożeniem zadań.

W (2) przypadku także każdy zwiadowca szuka robotnicy z najgorszym wynikiem. Także tu nie uwzględnia się
rozwiązań, które były już poprawiane.
Jedyną różnicą przy wszykiwaniu jest fakt, że najlepsze znalezione rozwiązanie może mieć dużą ilość prób poprawy.
Ze względu na wybrane kryterium możliwe byłoby zastąpienie najlepszego rozwiązania przez losowe. Dlatego 
dodatkowo sprawdzany jest warunek, czy dane rozwiązanie jest różne od najlepszego.

Podobnie jak w (1) przypadku, najgorsze rozwiązanie jest zastępowane losowym.

    \subsubsection{Pomocnicze funkcje}
\begin{itemize}
\item
\texttt{optimize}
Ta funkcja wykonuje głowną pętlę algortymu wywołując główne fazy algorytmu pszczelego:

\begin{lstlisting}
for (int i = 0; i < cycleCount_; i++) {
  sendEmployedBees();
  sendOnlookeerBees();
  sendScoutBees();
  best = getBestSolution();
  listener_.newResult(best.getSolution(), best.getEval());
}
\end{lstlisting}

Dodatkowo po każdej iteracji informuje GUI o nowym wyniku.

\item
\texttt{getBestSolution}
Funkcja zwraca najlepsze obliczone rozwiązanie.

\item
\texttt{insert} oraz \texttt{swap} funkcje pomocnicze przy etapie poszukiwania lokalnego oraz przy zmianie rozwiązań w funkcji mutate.
Są wykorzystywane odpowiednio w \texttt{insertLS} oraz \texttt{swapLS}.

\end{itemize}

  \subsection{Wyniki}
Algorytm testowaliśmy na przykładowych instancjach Tailarda.
Dla zestawu 50 x 5 (50 zadań na 5 maszynach) otrzymaliśmy następujące wyniki
dla domyślnych parametrów algorytmu:

\begin{center}
\begin{tabular}{|c|c|c|}
  \hline
  Wynik naszej implementecji & Najlepszy znany wynik & Różnica \\ \hline
  2724 & 2724 & 0 \\ \hline
  2848 & 2834 & 14 \\ \hline
  2635 & 2621 & 14 \\ \hline
  2762 & 2751 & 11 \\ \hline
  2863 & 2863 & 0 \\ \hline
  2829 & 2829 & 0 \\ \hline
  2732 & 2725 & 7 \\ \hline
  2691 & 2683 & 8 \\ \hline
  2564 & 2552 & 12 \\ \hline
  2782 & 2782 & 0 \\ \hline
\end{tabular}
\end{center}

Jak widać aż w 4 przypadkach uzyskaliśmy najlepszy znany wynik.

Po zmianie parametrów, dla testu drugiego uzyskaliśmy wyniki:

\begin{center}
\begin{tabular}{|c|c|c|}
  \hline
  Uzyskany czas & zmienione domyślnie parametru \\ \hline
  2838 & zwiększenie ilości zwiadowców do 30 \\ \hline
  2843 & zmiana opcji modyfikacji na 3 \\ \hline
\end{tabular}
\end{center}

Zmiana opcji modyfikacji na 0 - czyli jedna zamiana - spowodowała zmniejszenie zbieżności algorytmu i uzyskanie w tej samej ilości iteracji gorszych wyników
 (ok. 2860).
Wprowadzenie dodatkowej zamiany (opcja 2) nieznaczenie poprawiła zbieżność. Jednak można zauważyć, że lepsze wyniki daje
wstawianie niż zamiana zadań.
Z tego powodu opcja 4 - czyli losowy dobór metody zmiany - nie jest najlepszy.

Także znaczna ilość zwiadowców nie poprawia wyników - 50 zwiadowcom, przy 120 robotnicach, nie udało się polepszyć wyniku.
Natomiast taka ich ilość wydłużyła czas wykonania.

Także zmiana pozostałych współczynników nie poprawiła uzyskanego wcześniej wyniku:
\begin{itemize}
 \item Zmiana domyślnego trybu pracy zwiadowcy - poprawa najgorszego rozwiązania - na tryb
poprawy rozwiązania, którego najdłużej nie udało się polepszyć, nie poprawiła wyniku. Dla tego zestawu
testowego wynik wynosił ok. 2900.
 \item Ze względu na bardzo dużą złożoność lokalnej poprawy rozwiązań, nie udało nam się przeprowadzić testów 
z tą opcją.
\end{itemize}

Wyniki algorytmu dla większych danych testowych (przeprowadzone na domyślnych parametrach):

\begin{itemize}
 \item 50 zadań na 20 maszynach:

\begin{center}
\begin{tabular}{|c|c|c|}
  \hline
  Wynik naszej implementecji & Najlepszy znany wynik & Różnica \\ \hline
  4050 & 3800 & 250 \\ \hline
  3912 & 3680 & 132 \\ \hline
  3873 & 3610 & 263 \\ \hline
  3929 & 3680 & 249 \\ \hline
  3875 & 3570 & 305 \\ \hline
  3907 & 3670 & 237 \\ \hline
  3933 & 3690 & 243 \\ \hline
  3910 & 3640 & 270 \\ \hline
  3952 & 3720 & 232 \\ \hline
  3958 & 3720 & 238 \\ \hline
\end{tabular}
\end{center}

Dla tego zestawu testowego największa różnica wynosi 305, co stanowi ok. 7,8\% wyniku.

\item 100 zadań na 10 maszynach

\begin{center}
\begin{tabular}{|c|c|c|}
  \hline
  Wynik naszej implementecji & Najlepszy znany wynik & Różnica \\ \hline
  5918 & 5770 & 148 \\ \hline
  5482 & 5349 & 133 \\ \hline
  5754 & 5676 & 78 \\ \hline
  5958 & 5781 & 177 \\ \hline
  5668 & 5467 & 201 \\ \hline
  5395 & 5303 & 92 \\ \hline
  5726 & 5595 & 134 \\ \hline
  5755 & 5617 & 138 \\ \hline
  5983 & 5871 & 112 \\ \hline
  5940 & 5845 & 95 \\ \hline
\end{tabular}
\end{center}

W tym przypadku największy błąd stanowi ok. 3,5\% wyniku.



\item 200 zadań na 10 maszynach

\begin{center}
\begin{tabular}{|c|c|c|}
  \hline
  Wynik naszej implementecji & Najlepszy znany wynik & Różnica \\ \hline
  11020 & 10862 & 158 \\ \hline
  10777 & 10480 & 297 \\ \hline
  11139 & 10922 & 217 \\ \hline
  11000 & 10889 & 111 \\ \hline
  10800 & 10524 & 276 \\ \hline
  10582 & 10329 & 253 \\ \hline
  11081 & 10854 & 227 \\ \hline
  10974 & 10730 & 244 \\ \hline
  10690 & 10438 & 252 \\ \hline
  10868 & 10675 & 193 \\ \hline
\end{tabular}
\end{center}

Tutaj największy błąd stanowi ok. 2,7\%.

\end{itemize}


  \subsection{Wnioski}
Algorytm pszczeli pozwolił na uzyskanie wyników bliskich najlepszym, jakie udało się osiągnąć.
Oczywiście im więcej dłuższy był łączny czas wykonania, tym większe różnice w wynikach otrzymywaliśmy.
Jednak błąd względny wynosił ok. 5\% - tylko w pojedynczych testach różnice wynosiły do 8\%.
Można więc stwierdzić, że algorytm pszczeli daje bardzo dobre rezultaty.

Największy wpływ na wynik miała ilość zwiadowców, czyli znaczenie ma ile w każdej iteracji
dochodzi nowych, losowych rozwiązań. Także stopień modyfikacji rozwiązania, nieznaczenie,
ale wpływał na optymalizację wyniku.
Co interesujące, ilość iteracji nie jest najstotniejszym elementem algorytmu. W każdym przypadku
największa poprawa dokonuje się do ok. 800/1000 kroku. Powyżej tej wartości wynik nie ulega już
znaczącej poprawie.